package org.algorithm.biubiu.wheel_1.字符串;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @date 2022-04-13 星期三 00:00
 *输入一个字符串，打印出该字符串中字符的所有排列。
 *
 * 
 *
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 *
 * 
 *
 * 示例:
 *
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 字符串的排列 {
    public static void main(String[] args) {
        //System.out.println(permutation("abc"));//["abc","acb","bac","bca","cab","cba"]

    }

    /**
     * -----------------------------------------type-1   -----------------------------------------------------------
     * backTracking
     *
     * i = index 和 i= 0 的区别
     * i= 0 标准版 树形解析图 就是循环 a b c
     * i=index 指针直接跳到下次-求解所有子集
     * i=index  &&& step+1  两个指针可以指向字符串内所有可能的位置。 然后swap
     */
    List<String> res1 = new ArrayList();
    char[] arr1;
    public String[] permutation(String s) {

        if(s==null||s.length()==0){
            return null;
        }
        arr1 = s.toCharArray();
        backTracking(0);
        return res1.toArray(new String[res1.size()]);
    }

    public void backTracking(int step){
        String s ="";
        if(step== arr1.length-1){
            res1.add(String.valueOf(arr1));
            return;
        }
        Set<Character> set = new HashSet();
        for(int x = step; x< arr1.length; x++){
            if(set.contains(arr1[x])){
                continue;
            }
            set.add(arr1[x]);
            if(x!=step){
                swap(x,step);
            }
            backTracking(step+1);
            if(x!=step){
                swap(step,x);
            }
        }

    }



    public void swap(int index, int x){
        Character tmp;
        tmp = arr1[index];
        arr1[index] = arr1[x];
        arr1[x] = tmp;
    }
    /**
     * -----------------------------------------type-2   -----------------------------------------------------------
     *
     * 标准版 树形解析图 i = 0  就是循环 abc
     * backTrack  i = 0  &&  step +1  // 可以指向所有的位置  i 可以标准版的
     *
     */


    List<String> resList = new ArrayList();
    String data;
    public String[] permutation1(String s) {
        this.data  = s;

        boolean[] use = new boolean[s.length()];
        backTrack(0,use);

        String[] res = new String[resList.size()];
        resList.toArray(res);
        return res;
    }


    List<Character> cur = new ArrayList();
    public void backTrack(int step,boolean[] use){
        if(cur.size()==data.length()){
            resList.add(listToString(cur));
            return;
        }
        Set<Character> set = new HashSet();
        for(int i=0;i<data.length();i++){
            if(set.contains(data.charAt(i))) continue;
            if(use[i]==true) continue;
            use[i]= true;
            set.add(data.charAt(i));
            cur.add(data.charAt(i));
            backTrack(step+1,use);
            use[i]= false;
            cur.remove(cur.size()-1);
        }

    }



    public String listToString( List<Character> cur){
        String s = "";
        for(Character e:cur){
            s +=e;
        }
        return s;

    }

}
